#include "tools.cpp"
using namespace std;

void qsort(std::vector<int>& arr, int start, int end) {
    if (start >= end) return;
    int mid = arr[start];
    int low = start + 1, high = end;
    while (high >= low) {
        while (low <= high and arr[low] < mid) ++low;
        while (low <= high and arr[high] >= mid) --high;
        if (low > high) break;
        std::swap(arr[low], arr[high]);
        print(arr);
    }
    std::swap(arr[high], arr[start]);
    qsort(arr, start, high - 1);
    qsort(arr, high + 1, end);
}

int main() {
    std::vector<int> arr{3, 12, 4, 5, 2, 1, 3, 42, 3, 2, 123};
    qsort(arr, 0, arr.size());
    print(arr);
    return 0;
}
